{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## 1.5 \u5b9e\u73b0\u4e00\u4e2a\u4f18\u5148\u7ea7\u961f\u5217\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### \u95ee\u9898\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u600e\u6837\u5b9e\u73b0\u4e00\u4e2a\u6309\u4f18\u5148\u7ea7\u6392\u5e8f\u7684\u961f\u5217\uff1f \u5e76\u4e14\u5728\u8fd9\u4e2a\u961f\u5217\u4e0a\u9762\u6bcf\u6b21 pop \u64cd\u4f5c\u603b\u662f\u8fd4\u56de\u4f18\u5148\u7ea7\u6700\u9ad8\u7684\u90a3\u4e2a\u5143\u7d20"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### \u89e3\u51b3\u65b9\u6848\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u4e0b\u9762\u7684\u7c7b\u5229\u7528 heapq \u6a21\u5757\u5b9e\u73b0\u4e86\u4e00\u4e2a\u7b80\u5355\u7684\u4f18\u5148\u7ea7\u961f\u5217\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "import heapq\n\nclass PriorityQueue:\n    def __init__(self):\n        self._queue = []\n        self._index = 0\n\n    def push(self, item, priority):\n        heapq.heappush(self._queue, (-priority, self._index, item))\n        self._index += 1\n\n    def pop(self):\n        return heapq.heappop(self._queue)[-1]"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u4e0b\u9762\u662f\u5b83\u7684\u4f7f\u7528\u65b9\u5f0f\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "class Item:\n    def __init__(self, name):\n        self.name = name\n    def __repr__(self):\n        return 'Item({!r})'.format(self.name)\nq = PriorityQueue()\nq.push(Item('foo'), 1)\nq.push(Item('bar'), 5)\nq.push(Item('spam'), 4)\nq.push(Item('grok'), 1)\nq.pop()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "q.pop()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "q.pop()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "q.pop()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u4ed4\u7ec6\u89c2\u5bdf\u53ef\u4ee5\u53d1\u73b0\uff0c\u7b2c\u4e00\u4e2a pop() \u64cd\u4f5c\u8fd4\u56de\u4f18\u5148\u7ea7\u6700\u9ad8\u7684\u5143\u7d20\u3002\n\u53e6\u5916\u6ce8\u610f\u5230\u5982\u679c\u4e24\u4e2a\u6709\u7740\u76f8\u540c\u4f18\u5148\u7ea7\u7684\u5143\u7d20\uff08 foo \u548c grok \uff09\uff0cpop \u64cd\u4f5c\u6309\u7167\u5b83\u4eec\u88ab\u63d2\u5165\u5230\u961f\u5217\u7684\u987a\u5e8f\u8fd4\u56de\u7684\u3002"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### \u8ba8\u8bba\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u8fd9\u4e00\u5c0f\u8282\u6211\u4eec\u4e3b\u8981\u5173\u6ce8 heapq \u6a21\u5757\u7684\u4f7f\u7528\u3002\n\u51fd\u6570 heapq.heappush() \u548c heapq.heappop() \u5206\u522b\u5728\u961f\u5217 _queue \u4e0a\u63d2\u5165\u548c\u5220\u9664\u7b2c\u4e00\u4e2a\u5143\u7d20\uff0c\n\u5e76\u4e14\u961f\u5217 _queue \u4fdd\u8bc1\u7b2c\u4e00\u4e2a\u5143\u7d20\u62e5\u6709\u6700\u9ad8\u4f18\u5148\u7ea7\uff08 1.4 \u8282\u5df2\u7ecf\u8ba8\u8bba\u8fc7\u8fd9\u4e2a\u95ee\u9898\uff09\u3002\nheappop() \u51fd\u6570\u603b\u662f\u8fd4\u56de\u201d\u6700\u5c0f\u7684\u201d\u7684\u5143\u7d20\uff0c\u8fd9\u5c31\u662f\u4fdd\u8bc1\u961f\u5217pop\u64cd\u4f5c\u8fd4\u56de\u6b63\u786e\u5143\u7d20\u7684\u5173\u952e\u3002\n\u53e6\u5916\uff0c\u7531\u4e8e push \u548c pop \u64cd\u4f5c\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a O(log N)\uff0c\u5176\u4e2d N \u662f\u5806\u7684\u5927\u5c0f\uff0c\u56e0\u6b64\u5c31\u7b97\u662f N \u5f88\u5927\u7684\u65f6\u5019\u5b83\u4eec\u8fd0\u884c\u901f\u5ea6\u4e5f\u4f9d\u65e7\u5f88\u5feb\u3002"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u5728\u4e0a\u9762\u4ee3\u7801\u4e2d\uff0c\u961f\u5217\u5305\u542b\u4e86\u4e00\u4e2a (-priority, index, item) \u7684\u5143\u7ec4\u3002\n\u4f18\u5148\u7ea7\u4e3a\u8d1f\u6570\u7684\u76ee\u7684\u662f\u4f7f\u5f97\u5143\u7d20\u6309\u7167\u4f18\u5148\u7ea7\u4ece\u9ad8\u5230\u4f4e\u6392\u5e8f\u3002\n\u8fd9\u4e2a\u8ddf\u666e\u901a\u7684\u6309\u4f18\u5148\u7ea7\u4ece\u4f4e\u5230\u9ad8\u6392\u5e8f\u7684\u5806\u6392\u5e8f\u6070\u5de7\u76f8\u53cd\u3002"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "index \u53d8\u91cf\u7684\u4f5c\u7528\u662f\u4fdd\u8bc1\u540c\u7b49\u4f18\u5148\u7ea7\u5143\u7d20\u7684\u6b63\u786e\u6392\u5e8f\u3002\n\u901a\u8fc7\u4fdd\u5b58\u4e00\u4e2a\u4e0d\u65ad\u589e\u52a0\u7684 index \u4e0b\u6807\u53d8\u91cf\uff0c\u53ef\u4ee5\u786e\u4fdd\u5143\u7d20\u6309\u7167\u5b83\u4eec\u63d2\u5165\u7684\u987a\u5e8f\u6392\u5e8f\u3002\n\u800c\u4e14\uff0c index \u53d8\u91cf\u4e5f\u5728\u76f8\u540c\u4f18\u5148\u7ea7\u5143\u7d20\u6bd4\u8f83\u7684\u65f6\u5019\u8d77\u5230\u91cd\u8981\u4f5c\u7528\u3002"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u4e3a\u4e86\u9610\u660e\u8fd9\u4e9b\uff0c\u5148\u5047\u5b9a Item \u5b9e\u4f8b\u662f\u4e0d\u652f\u6301\u6392\u5e8f\u7684\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "a = Item('foo')\nb = Item('bar')\na < b"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u5982\u679c\u4f60\u4f7f\u7528\u5143\u7ec4 (priority, item) \uff0c\u53ea\u8981\u4e24\u4e2a\u5143\u7d20\u7684\u4f18\u5148\u7ea7\u4e0d\u540c\u5c31\u80fd\u6bd4\u8f83\u3002\n\u4f46\u662f\u5982\u679c\u4e24\u4e2a\u5143\u7d20\u4f18\u5148\u7ea7\u4e00\u6837\u7684\u8bdd\uff0c\u90a3\u4e48\u6bd4\u8f83\u64cd\u4f5c\u5c31\u4f1a\u8ddf\u4e4b\u524d\u4e00\u6837\u51fa\u9519\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "a = (1, Item('foo'))\nb = (5, Item('bar'))\na < b"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "c = (1, Item('grok'))\na < c"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u901a\u8fc7\u5f15\u5165\u53e6\u5916\u7684 index \u53d8\u91cf\u7ec4\u6210\u4e09\u5143\u7ec4 (priority, index, item) \uff0c\u5c31\u80fd\u5f88\u597d\u7684\u907f\u514d\u4e0a\u9762\u7684\u9519\u8bef\uff0c\n\u56e0\u4e3a\u4e0d\u53ef\u80fd\u6709\u4e24\u4e2a\u5143\u7d20\u6709\u76f8\u540c\u7684 index \u503c\u3002Python \u5728\u505a\u5143\u7ec4\u6bd4\u8f83\u65f6\u5019\uff0c\u5982\u679c\u524d\u9762\u7684\u6bd4\u8f83\u5df2\u7ecf\u53ef\u4ee5\u786e\u5b9a\u7ed3\u679c\u4e86\uff0c\n\u540e\u9762\u7684\u6bd4\u8f83\u64cd\u4f5c\u5c31\u4e0d\u4f1a\u53d1\u751f\u4e86\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "a = (1, 0, Item('foo'))\nb = (5, 1, Item('bar'))\nc = (1, 2, Item('grok'))\na < b"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "a < c"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u5982\u679c\u4f60\u60f3\u5728\u591a\u4e2a\u7ebf\u7a0b\u4e2d\u4f7f\u7528\u540c\u4e00\u4e2a\u961f\u5217\uff0c\u90a3\u4e48\u4f60\u9700\u8981\u589e\u52a0\u9002\u5f53\u7684\u9501\u548c\u4fe1\u53f7\u91cf\u673a\u5236\u3002\n\u53ef\u4ee5\u67e5\u770b 12.3 \u5c0f\u8282\u7684\u4f8b\u5b50\u6f14\u793a\u662f\u600e\u6837\u505a\u7684\u3002"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "heapq \u6a21\u5757\u7684\u5b98\u65b9\u6587\u6863\u6709\u66f4\u8be6\u7ec6\u7684\u4f8b\u5b50\u7a0b\u5e8f\u4ee5\u53ca\u5bf9\u4e8e\u5806\u7406\u8bba\u53ca\u5176\u5b9e\u73b0\u7684\u8be6\u7ec6\u8bf4\u660e\u3002"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.7.1"
    },
    "toc": {
      "base_numbering": 1,
      "nav_menu": {},
      "number_sections": true,
      "sideBar": true,
      "skip_h1_title": true,
      "title_cell": "Table of Contents",
      "title_sidebar": "Contents",
      "toc_cell": false,
      "toc_position": {},
      "toc_section_display": true,
      "toc_window_display": true
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}